package seach

//小根堆向下调整
func SSift(li []int, top, end int) {
	i := top
	currTopVal := li[i]
	j := i*2 + 1
	for j <= end {
		if j+1 <= end && li[j+1] < li[j] {
			j++
		}
		if li[j] < currTopVal {
			li[i] = li[j]
			i = j
			j = i*2 + 1
		} else {
			break
		}
	}
	li[i] = currTopVal

}

//大根堆调整
func Sift(li []int, top, end int) {
	i := top
	currTopVal := li[i]
	j := i*2 + 1
	for j <= end {
		if j+1 <= end && li[j+1] > li[j] {
			j++
		}
		if li[j] > currTopVal {
			li[i] = li[j]
			i = j
			j = i*2 + 1
		} else {
			break
		}
	}
	li[i] = currTopVal

}

//大根堆排序
func HeapSort(li []int) {
	lastIndex := len(li) - 1
	lastFather := (lastIndex - 1) / 2
	//从最后一个父节点开始向下调整
	for i := lastFather; i >= 0; i-- {
		Sift(li, i, lastIndex)
	}
	//出数
	for i := lastIndex; i >= 0; i-- {
		li[0], li[i] = li[i], li[0]
		Sift(li, 0, i-1)
	}
}

func TopK(li []int, k int)([]int) {
	heap :=make([]int,0,k)
	heap = append(heap,li[0:k]...)
	lastIndex := len(heap) - 1
	lastFater := (lastIndex - 1) / 2
	for i := lastFater; i >= 0; i-- {
		SSift(heap, i, lastIndex)
	}
	for i := k; i < len(li); i++ {
		if li[i] > heap[0] {
			heap[0] = li[i]
			SSift(heap, 0, lastIndex)
		}
	}

	//出数
	for i:=lastIndex;i>=0;i-- {
		heap[0],heap[i]=heap[i],heap[0]
		SSift(heap,0,i-1)
	}
	return heap
}
func SHeapSort(li []int) {
	lastIndex := len(li) - 1
	lastFather := (lastIndex - 1) / 2
	//从最后一个父节点开始向下调整
	for i := lastFather; i >= 0; i-- {
		SSift(li, i, lastIndex)
	}
	//出数
	for i := lastIndex; i >= 0; i-- {
		li[0], li[i] = li[i], li[0]
		SSift(li, 0, i-1)
	}
}
